#include <iostream>
#include <vector>
using namespace std;

//class Solution {
//public:
//    int pivotIndex(vector<int>& nums) {
//        int n = nums.size();
//        vector<int> dp(n + 1);
//        for (int i = 1; i <= n; ++i) {
//            dp[i] = dp[i - 1] + nums[i - 1];
//        }
//        for (int i = 1; i <= n; ++i) {
//            if (dp[i - 1] == (dp[n] - dp[i])) {
//                return i - 1;
//            }
//        }
//        return -1;
//    }
//};


class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        vector<int> result;
        int n = nums.size();
        vector<int> dp(n + 1);
        dp[1] = nums[0];
        int mul = nums[0];
        for (int i = 2; i <= n; ++i) {
            dp[i] = dp[i - 1] * nums[i - 1];
            mul *= nums[i - 1];
        }
        for (int i = 1; i <= n; ++i) {
            int ret = mul - dp[i] + dp[i - 1];
            result.push_back(ret);
        }
        return result;
    }
};